//
// Created by ASUS on 2024/3/19.
//

#include <bits/stdc++.h>
using namespace std;

int _01dp(vector<int>& w, vector<int>& v, int target){
	int n=w.size();
	vector<vector<int>> f(n+1,vector<int>(target+1,0));
	for(int i=0;i<n;i++){
		for(int j=target;j>=w[i];j--){
			f[i+1][j]=max(f[i][j],f[i][j-w[i]]+v[i]);
		}
	}
	return f[n][target];
}
//至多装满最大价值
int _01dp_1(vector<int>& w, vector<int>& v, int target){
	int n=w.size();
	vector<int> f(target+1,0);
	for(int i=0;i<n;i++){
		for(int j=target;j>=w[i];j--){
			f[j]=max(f[j],f[j-w[i]]+v[i]);
		}
	}
	return f[target];
}

//恰好装满的方案数
int plan(vector<int>& w, int target){
	vector<int> f(target+1);//选择物品总容量为target的方案数
	f[0]=1;
	for(int x:w){
		for(int j=target;j>=x;j--){
			f[j]+=f[j-x];
		}
	}
	return f[target];
}
//至少装满最小花费
int _01dp_2(vector<int>& w, vector<int>& v, int target){
	int n=w.size();
	vector<int> f(target+1,INT_MAX/2);
	f[0]=0;
	for(int i=0;i<n;i++){
		for(int j=target;j;j--){
			f[j]=min(f[j],f[max(j-w[i],0)]+v[i]);
		}
	}
	return f[target];
}


int main(){
	vector<int> w={1,1,2,3,5};
	vector<int> v={10,10,30,10,50};
	int target=5;
	cout<<_01dp_2(w,v,target)<<endl;
	cout<<plan(w,target)<<endl;
}